package com.leetcode;

/**
 * 76. 最小覆盖子串
 */
public class Solution76 {

    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }
        int[] tCount = new int[128];
        int[] sCount = new int[128];
        for (int i = 0; i < t.length(); i++) {
            tCount[t.charAt(i) - 'A']++;
        }
        int l = 0;
        int r = -1;
        int minLength = s.length() + 1;
        String minStr = "";
        while (l < s.length()) {
            if (contain(sCount, tCount)) {
                if (r - l + 1 < minLength) {
                    minLength = r - l + 1;
                    minStr = s.substring(l, r + 1);
                }
                sCount[s.charAt(l) - 'A']--;
                l++;
            } else if (r + 1 < s.length()) {
                ++r;
                sCount[s.charAt(r) - 'A']++;
            } else {
                break;
            }
        }
        return minStr;
    }

//    private int indexOf(char[] checkChar, char ch) {
//        for (int i = 0; i < checkChar.length; i++) {
//            if (ch == checkChar[i]) {
//                return i;
//            }
//        }
//        return -1;
//    }

    private boolean contain(int[] sCount, int[] tCount) {
        for (int i = 0; i < 128; i++) {
            if (sCount[i] < tCount[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
//        String s = "ADOBECODEBANC";
//        String t = "ABC";
        String s = "bbaac";
        String t = "aba";
        String res = new Solution76().minWindow(s, t);
        System.out.println(res);
    }

}
